Sommets, arêtes, arcs, ordre

Définitions   Graphe, sommets, arêtes, boucle, graphe orienté, arcs

• Un graphe  \(G\) est constitué d’un ensemble  \(S=\{s_1~; s_2~;\cdots~; s_n\}\) de points appelés sommets, et d’un ensemble  \(A=\{a_1~;a_2~;\cdots~;a_p\}\) d’arêtes, tels qu’à chaque arête  \(a_k\) on associe deux éléments de  \(S\) appelés ses extrémités.
  
• Si les deux extrémités d’une arête sont confondues, l’arête est appelée une boucle.
  

Remarque

Si l’ordre des extrémités est pris en compte, on parle de graphe orienté ; les arêtes sont alors
appelées arcs et on représente alors le sens de parcours sur ces arcs avec des flèches.

Une façon de visualiser la complexité d’un graphe est de compter ses sommets et le nombre d’arêtes qui partent ou arrivent à chaque sommet.

Exemple

Le graphe suivant est orienté ; ce sont donc des arcs (et non des arêtes) qui relient les sommets.
Le sommet n° 2 a trois arcs sortants (qui vont aux sommets n° 1, n° 3 et n° 4) et un arc entrant (qui vient du sommet n° 6). Son degré sortant est donc 3 et son degré entrant est 1.

Définition Ordre d’un graphe

L’ordre du graphe  \(G\) est le nombre de ses sommets.

Remarques

1. Deux arêtes qui ont les mêmes extrémités sont dites parallèles.

2. Un graphe se dessine, mais :

• il y a plusieurs dessins possibles pour un même graphe ;
  
• il est important de bien matérialiser les sommets (souvent par des points), car on est parfois obligé de faire croiser deux arêtes sans qu’il y ait de sommet.
  

Exemples

1.  \(G_2\) et  \(G_3\) représentent le même graphe à 4 sommets et 6 arêtes.

2. \(G_4\) et  \(G_5\) représentent le même graphe à  \(5\) sommets et  \(5\) arêtes.

3. \(G_6\) et  \(G_8\) représentent le même graphe, mais pas  \(G_7\) , pourtant ils ont tous  \(6\) sommets et  \(9\) arêtes.

 4. Ce graphe possède 5 sommets : A, B, C, D et E. On dit donc que ce graphe est d'ordre 5. Ce graphe possède 4 arêtes.